package test;

import java.util.Stack;

/**
 * @Author Stringzhua
 * @Date 2024/11/7 23:22
 * description: 使用非递归的方式,实现一个二叉树的后序遍历
 * LRD先遍历左子树，再遍历右子树，最后访问根节点
 */
class Node {
    int val;
    Node left;
    Node right;

    // 构造函数，用于创建一个新的二叉树节点，初始化节点的值，并将左右子树设为null
    Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class Demo03 {
    public static void main(String[] args) {
        // 构建一个完整赋值的二叉树示例
        Node tree = new Node(1);
        tree.left = new Node(2);
        tree.right = new Node(3);
        tree.right.left = new Node(4);
        tree.right.right = new Node(5);

        // 调用LRD方法对构建好的二叉树进行后序遍历
        LRD(tree);
    }

    /**
     * 实现二叉树的后序遍历
     * @param tree 要进行后序遍历的二叉树的根节点
     */
    public static void LRD(Node tree) {
        // 判空
        if (tree == null) {
            return;
        }

        // 创建一个栈
        Stack<Node> stack = new Stack<>();
        // 用于记录上一次访问过的节点，初始化为null
        Node lastvisit = null;

        while (tree!= null ||!stack.isEmpty()) {
            // 将当前节点的左子树节点依次入栈
            while (tree!= null) {
                stack.push(tree);
                tree = tree.left;
            }

            // 从栈中弹出一个节点,此时该节点可能是出栈的节点
            tree = stack.pop();

            // 如果右子树为空或右子树已经被访问过(lastvisit为false)
            if (tree.right == null || tree.right == lastvisit) {
                System.out.print(tree.val + " ");//输出该节点
                // 更新状态表示当前节点已被访问过
                lastvisit = tree;
                // 将tree初始化
                tree = null;
            } else {
                // 如果右子树不为空且未被访问过则该节点重新压入栈中
                stack.push(tree);
                // 然后将当前节点设置为其右子树节点,继续遍历右子树
                tree = tree.right;
            }
        }
    }
}